package com.sx.sx1.lintcode.day717;

import java.util.LinkedList;
import java.util.Queue;

public class LC3701 {


    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }


    static class Solution {
        /**
         * @param root: The root of the binary tree
         * @param u:    A node in root
         * @return: Node value of the right node
         */
        public int findNearestRightNode(TreeNode root, TreeNode u) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);

            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    TreeNode pop = q.poll();
                    if (pop == u) {
                        if (i == size - 1) return -1;
                        else return q.poll().val;
                    }

                    if (pop.left != null) {
                        q.add(pop.left);
                    }

                    if (pop.right != null) {
                        q.add(pop.right);
                    }
                }
            }
            return -1;
        }
    }
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
3701 · 找到二叉树中最近的右侧节点预发布
算法
中等
通过率
60%

题目
题解2
笔记
讨论1
排名
记录
该题目为预发布题目，如遇到任何问题，请及时通过"题目纠错"联系我们，我们会升级您的账号为VIP作为感谢。
描述
给定一棵二叉树的根节点 root 和树中的一个节点 u，返回节点 u 所在的层中与其距离最近的右侧节点的节点值 val，若节点 u 是当前层最右侧的节点，则返回 -1 。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


节点总个数在
[

1
,

1
0
4

]
[ 1, 10
4
  ] 之间
1
≤
n
o
d
e
.
v
a
l
≤
1
0
4
1≤node.val≤10
4

树中的所有节点的节点值是唯一的
u 是以 root 为根的二叉树的一个节点

样例
样例 1：

输入：
root = {1,2,3,#,4,5,6}
u = 2
输出：
3
解释：
如图，在节点 2 所在层，与之最近的右侧节点是节点 3
3701_1.png

样例 2：

输入：
root = {3,1,#,#,2}
u = 1
输出：
-1
解释：
如图，节点 1 所在的层数仅有一个节点，没有找到最近的右侧节点
3701_2.png

标签
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
83/1859
已开启智能提示
发起考试
30 分 00 秒
12345678910111213141516171819202122
    }
}
控制台
历史提交

 */
